{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# 习题11.3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "写出条件随机场模型学习的梯度下降法。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 解答：  \n",
    "条件随机场的对树极大似然函数为：$$L(w)=\\sum^N_{j=1}\\sum^K_{k=1}w_kf_k(y_j,x_j)-\\sum^N_{j=1}\\log{Z_w(x_j)}$$\n",
    "因此梯度下降算法的目标函数就是：$f(w)=-L(w)$  \n",
    "目标函数的梯度函数为：$$g(w)=\\frac{\\nabla{f(w)}}{\\nabla{w}}=(\\frac{\\partial{f(w)}}{\\partial{w_1}},\\frac{\\partial{f(w)}}{\\partial{w_2}},\\cdots,\\frac{\\partial{f(w)}}{\\partial{w_k}})$$\n",
    "$$% <![CDATA[\n",
    "\\begin{equation}\n",
    "\\begin{split}\n",
    "\\frac{\\partial{f(w)}}{\\partial{w_i}}&=-\\sum^N_{j=1}w_if_i(y_j,x_j)+\\sum^N_{j=1}\\frac{1}{Z_w(x_j)}\\cdot\\frac{\\partial{Z_w(x_j)}}{\\partial{w_i}}\\\\\n",
    "&=-\\sum^N_{j=1}w_if_i(y_j,x_j)+\\sum^N_{j=1}\\frac{1}{Z_w(x_j)}\\sum_y(\\exp{\\sum^K_{k=1}w_kf_k(y,x_j))}w_if_i(y,x_j)\n",
    "\\end{split}\n",
    "\\end{equation} %]]>$$  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "按照梯度下降算法：  \n",
    "__(1)__ 取初始值$w^{(0)}\\in{R^k}$，置$t=0$  \n",
    "__(2)__ 计算$f(w^{(t)})$  \n",
    "__(3)__ 计算梯度$g_t=g(w^{(t)})$，当$% <![CDATA[ \n",
    "\\|g_t\\|<\\epsilon %]]>$，停止迭代，令$w^*=w^{(k)}$；否则，令$p_t=-g(w^{(t)})$，求$\\lambda_t$，使$$f(w^{(t)}+\\lambda_tp_t)=\\min_{\\lambda\\ge0}{f(w^{(t)}+\\lambda{p_t})}$$\n",
    "__(4)__ 置$w^{(t+1)}=w^{(t)}+\\lambda_tp_t$，计算$f(w^{(t+1)})$  \n",
    "当$% <![CDATA[\n",
    "\\|f(w^{(t+1)})-f(w^{(t)})\\|<\\epsilon %]]>$或$% <![CDATA[\n",
    "\\|w^{(t+1)}-w^{(t)}\\|<\\epsilon %]]>$时，停止迭代，令$w^*=w^{(t+1)}$  \n",
    "__(5)__ 否则，置$t=t+1$，转__(3)__ "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 习题11.4"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "参考图11.6的状态路径图，假设随机矩阵$M_1(x),M_2(x),M_3(x),M_4(x)$分别是\n",
    "$$% <![CDATA[\n",
    "M_1(x)=\\begin{bmatrix}0&0\\\\0.5&0.5\\end{bmatrix} ,%]]>% <![CDATA[\n",
    "M_2(x)=\\begin{bmatrix}0.3&0.7\\\\0.7&0.3\\end{bmatrix}%]]>$$\n",
    "$$% <![CDATA[\n",
    "M_3(x)=\\begin{bmatrix}0.5&0.5\\\\0.6&0.4\\end{bmatrix},%]]>% <![CDATA[\n",
    "M_4(x)=\\begin{bmatrix}0&1\\\\0&1\\end{bmatrix} %]]>$$\n",
    "求以$start=2$为起点$stop=2$为终点的所有路径的状态序列$y$的概率及概率最大的状态序列"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 创建随机矩阵"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[[0, 0], [0.5, 0.5]], [[0.3, 0.7], [0.7, 0.3]], [[0.5, 0.5], [0.6, 0.4]], [[0, 1], [0, 1]]]\n"
     ]
    }
   ],
   "source": [
    "M1 = [[0,0],[0.5,0.5]] \n",
    "M2 = [[0.3, 0.7], [0.7,0.3]]\n",
    "M3 = [[0.5, 0.5], [0.6, 0.4]]\n",
    "M4 = [[0, 1], [0, 1]]\n",
    "M = [M1, M2, M3, M4]\n",
    "print(M)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 生成路径"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[array([2, 1, 1, 1, 2]), array([2, 1, 1, 2, 2]), array([2, 1, 2, 1, 2]), array([2, 1, 2, 2, 2]), array([2, 2, 1, 1, 2]), array([2, 2, 1, 2, 2]), array([2, 2, 2, 1, 2]), array([2, 2, 2, 2, 2])]\n"
     ]
    }
   ],
   "source": [
    "path = [2]\n",
    "for i in range(1,4):\n",
    "    paths = []\n",
    "    for _, r in enumerate(path):\n",
    "        temp = np.transpose(r)\n",
    "        paths.append(np.append(temp, 1))\n",
    "        paths.append(np.append(temp, 2))\n",
    "    path = paths.copy()\n",
    "\n",
    "path = [np.append(r, 2) for _, r in enumerate(path)]\n",
    "print(path)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 计算概率"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[([2, 1, 2, 1, 2], 0.21), ([2, 2, 1, 1, 2], 0.175), ([2, 2, 1, 2, 2], 0.175), ([2, 1, 2, 2, 2], 0.13999999999999999), ([2, 2, 2, 1, 2], 0.09), ([2, 1, 1, 1, 2], 0.075), ([2, 1, 1, 2, 2], 0.075), ([2, 2, 2, 2, 2], 0.06)]\n"
     ]
    }
   ],
   "source": [
    "pr = []\n",
    "for _, row in enumerate(path):\n",
    "    p = 1\n",
    "    for i in range(len(row)-1):\n",
    "        a = row[i]\n",
    "        b = row[i+1]\n",
    "        p *= M[i][a-1][b-1]\n",
    "    pr.append((row.tolist(), p))\n",
    "pr = sorted(pr, key=lambda x : x[1], reverse=True)\n",
    "print(pr)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 打印结果"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "以start=2为起点stop=2为终点的所有路径的状态序列y的概率为：\n",
      "    路径为：2->1->2->1->2 概率为：0.21\n",
      "    路径为：2->2->1->1->2 概率为：0.175\n",
      "    路径为：2->2->1->2->2 概率为：0.175\n",
      "    路径为：2->1->2->2->2 概率为：0.13999999999999999\n",
      "    路径为：2->2->2->1->2 概率为：0.09\n",
      "    路径为：2->1->1->1->2 概率为：0.075\n",
      "    路径为：2->1->1->2->2 概率为：0.075\n",
      "    路径为：2->2->2->2->2 概率为：0.06\n",
      "概率[0.21]最大的状态序列为：2->1->2->1->2 "
     ]
    }
   ],
   "source": [
    "print(\"以start=2为起点stop=2为终点的所有路径的状态序列y的概率为：\")\n",
    "for path, p in pr:\n",
    "    print(\"    路径为：\" + \"->\".join([ str(x) for x in path]) ,end=\" \")\n",
    "    print(\"概率为：\" + str(p))\n",
    "print(\"概率[\" + str(pr[0][1]) +\"]最大的状态序列为：\" + \"->\".join([str(x) for x in pr[0][0]]), end = \" \")"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.2"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": false,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
